package cym;

public class StraightInsertionSort {

    public static void sort(int[] r) {
        int n = r.length;
        //n-1趟排序
        for (int i = 1; i <= n - 1; i++) {
            int j;
            int temp = r[i];
            //将小于r[i]的记录向后移
            for (j = i - 1; j >= 0 && temp < r[j]; j--) {
                r[j + 1] = r[j];
            }
            //j+1就是正确的位置
            r[j + 1] = temp;
        }
    }

    public static void display(int[] r) {
        for (int item : r) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] r = new int[]{3, 5, 5, 4, 120, 43, 1, 76, 78, 12, 346};
        StraightInsertionSort.sort(r);
        StraightInsertionSort.display(r);
    }

}